#pragma once
#include "sort.h"
template<class T>

class QuickSort :
	public Sort<T>
{
public:
	void sortArray(T * t,int k)
	{
		int l=0;
		int r=k;
		quicksort(t,l,r);
	}
	void quicksort(T A[],int l,int r)
	{
		 if(l>=r) return;
		 int i=l;
		 int j=r;
		 T x=A[(l+r)/2];//x=A[random(l-r)]
		 while(i<=j)
		 {
					while(A[i]<x) i++;
					while(A[j]>x) j--;
					if(i<=j)
					{
							T temp=A[i];
							A[i]=A[j];
							A[j]=temp;
							i++;j--;
					}
		 }
		 quicksort(A,l,j);
		 quicksort(A,i,r);
	}
	QuickSort(void)
	{
	}
	~QuickSort(void)
	{
	}
};
